一、題目介紹
今天要解的題目是LeetCode的Binary Tree Inorder Traversal，中文可以稱為「二元樹中序走訪」。

在Binary Tree中，常見的Tree Traversal（樹的走訪）方式包括：

• Preorder Traversal（前序走訪）
• Inorder Traversal（中序走訪）
• Postorder Traversal（後序走訪）
• Level Order Traversal（層序走訪）
  今天要學習的是其中的Inorder Traversal。

中序走訪的順序為左子樹 → 根節點 → 右子樹
也就是Left → Root → Right

例如有以下二元樹

進行中序走訪
先走左子樹
↓
再走根節點
↓
最後走右子樹

實際順序為 1 → 3 → 2
因此答案為 [1, 3, 2]

二、解題思路
這題可以使用DFS（Depth-First Search，深度優先搜尋）搭配遞迴（Recursion）完成。

因為Inorder Traversal的規則非常明確左 → 根 → 右

所以對於每一個節點，可以依照以下順序處理
1. 先走訪左子樹
如果目前節點有左子樹，就先繼續往左走。

2. 處理目前節點
左子樹走完之後，再將目前節點的值加入結果。

3. 最後走訪右子樹
處理完目前節點後，再繼續走訪右子樹。

三、解題流程
以以下二元樹為例

從1開始
Step 1：處理節點 1
先尋找左子樹
節點1沒有左子樹，因此接著加入1
結果：[1]

Step 2：處理節點 2
接著進入節點2
節點2有左子樹3，因此先處理3
節點3沒有左子樹，因此加入3
結果：[1, 3]

處理完3後回到2，加入2
結果：[1, 3, 2]

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 時間複雜度：O(n)
  • 每個節點都會被走訪一次，因此如果樹中共有n個節點，就需要處理n個節點。
  • 所以時間複雜度為：O(n)
• 空間複雜度：O(n)
  • 這裡需要注意，除了遞迴Call Stack之外，還需要使用List儲存所有節點的結果。
  • 結果本身需要O(n)的空間。
  • 因此整體空間複雜度為：O(n)
  • 其中遞迴Call Stack本身為O(h)，h為二元樹高度。

Python

• 時間複雜度：O(n)
  • 每個節點只會被走訪一次，因此時間複雜度為O(n)。
• 空間複雜度：O(n)
  • 需要使用result List儲存所有節點的值，因此需要O(n)空間。
  • 另外遞迴也會使用 Call Stack，其空間為O(h)。
  • 由於結果 List 本身已經需要O(n)，因此整體空間複雜度為：O(n)

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天學習了Binary Tree的Inorder Traversal（中序走訪），也進一步了解Tree Traversal的基本概念。

之前 Day 09 的 Maximum Depth of Binary Tree使用DFS計算樹的最大深度，而今天則是使用DFS依照指定順序走訪整棵樹。

Inorder Traversal最重要的就是記住：

Left → Root → Right 左 → 根 → 右

只要掌握這個順序，就能理解整個遞迴流程。

今天也讓我發現，遞迴不只是「一直呼叫自己」，更重要的是呼叫的順序會決定最後得到的結果。如果把加入節點的位置改變，就會形成不同的Tree Traversal，例如前序或後序走訪。

另外，這題也讓我開始接觸Tree Traversal的概念。之後如果遇到需要依照不同順序處理Binary Tree的題目，就可以先思考應該使用哪一種走訪方式，再設計對應的演算法。